package q1051_heightChecker;

public class Solution_2 {
    /*
    还有一种巧妙的方法
    题目中已经设置了人数的范围是100个以内
    所以可以创建一个101数组（或者求出身高最大值然后创建最大值个数的数组）
    而后在数组中记录不同身高的各有多少个 也就是arr[height]++;
    在这之后 我们并不需要排序
    只需要在满足int j = 1; j <= arr[i]时 循环的比当前height数组中的idx位置是否与i相等
    如果不想等则ans++
    这里是利用了数组已经帮我们进行了一定的排序功能
    有序的比较错位情况
     */
    public int heightChecker(int[] heights) {

        int[] arr = new int[101];
        for (int height : heights) arr[height]++;
        int ans = 0, idx = 0;
        for (int i = 1; i <= arr.length; i++) {
            for (int j = 1; j <= arr[i]; ++j) {
                ans += heights[idx++] == i ? 0 : 1;
            }
        }
        return ans;
    }
}
